1. Field of the Invention
The present invention generally relates to computer systems, and more particularly to a method of handling competing requests for data processing resources using arbitration.
2. Description of the Related Art
In the early days of computing, system designs were relatively simple with components essentially connecting directly to their necessary data processing resources. For example, the earliest computers used only a single processor which directly accessed a memory bank and peripheral devices such as a keyboard and display. Because the various resources were dedicated to use by a single component, there was no concern with device contention wherein multiple components might attempt to simultaneously access a single resource. Modern computer systems, however, rely on an increasing number of components which must compete for shared resources. For example, state-of-the-art systems now utilize multiple processors which must vie for access to system memory blocks residing in shared memory caches. If two or more processors issue contemporary requests (read or write operations) which access the same memory block, care must be taken to ensure the integrity of the value (program instruction or operand data) stored in that memory block. Another useful example is the peripheral component interconnect (PCI) architecture in which input/output devices act as masters to access a communications link (i.e., a PCI bus). Any device on a PCI bus that is capable of acting as a bus master may initiate a transaction with any other device, but only one transaction can be placed on the bus at a time.
These potential conflicts in accessing shared resources are typically handled using arbitration circuitry which serializes the requests, i.e., the arbiter will allow one of the requesters to continue its transaction, while the other requester(s) must wait, according to various arbitration protocols. This arbitration process is generally illustrated in FIG. 1 showing four finite state machines (FSMs) 2a, 2b, 2c, 2d which may attempt to access a shared resource 6 from time to time. Instead of directly accessing shared resource 6, the FSMs send their requests to arbitration logic 4. Arbitration logic 4 will select one of the competing requests from the FSMs and issue a grant signal to that winning requester, and will issue wait signals to the other requesters. The other requesters must accordingly retry their transactions in later clock cycles. Different access priorities may be assigned to the requesting devices in order to simplify the decision of the arbiter. If multiple simultaneous requesters have the same access priority, the arbitration logic can sequentially grant access based on numeric identifiers assigned to each requesting device, or using time-slicing methods which attempt to fairly distribute access across the multiple requesters. In the depicted example, arbitration logic 4 grants access for FSM0 2a to shared resource 6 when four requests are received by arbitration logic 4 simultaneously from the four requesters.
When a new computer system is designed, it is important to ensure that the design is going to work properly before proceeding with fabrication preparation for the integrated circuit devices, and their assembly into the finished system. A variety of tests can be performed to evaluate the design, but simulation remains the dominant strategy for functionally verifying high-end computer systems. A design-under-test is driven by vectors of inputs, and states encountered while walking through the sequence are checked for properties of correctness. This process is often performed by software simulation tools using different programming languages created for electronic design automation, including Verilog, VHDL and TDML. The verification process should include simulation of any arbitration logic in the design. Arbitration logic is usually in a critical timing path, and if any requesting devices have logic errors or manufacturing defects, or are driven beyond their design speeds, arbitration may break down. Conventional verification techniques predominantly rely on random traffic patterns to test the operation of arbitration logic.